package Dijkstra算法;

import java.util.Arrays;
import java.util.Scanner;

/**
 * @author: AirMan
 * @date: 2025/6/8 13:55
 * @description:
 */
public class Main {
    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);

        int v = sc.nextInt();
        int e = sc.nextInt();

        int[][] grid = new int[v + 1][v + 1];
        for (int i = 0; i < v; i++) {
            Arrays.fill(grid[i], Integer.MAX_VALUE);
        }
        for (int i = 0; i < e; i++) {
            int v1 = sc.nextInt();
            int v2 = sc.nextInt();
            int value = sc.nextInt();
            grid[v1][v2] = value;
        }

        int[] miniDist = new int[v + 1]; // 节点到源点的最短距离
        Arrays.fill(miniDist, Integer.MAX_VALUE);
        miniDist[1] = 0; // 源节点

        boolean[] visited = new boolean[v + 1]; // 访问数组

        for (int i = 1; i <= v; i++) {
            int miniVal = Integer.MAX_VALUE;
            int curNode = 1;
            // 1.选取距离源节点最近的节点
            for (int j = 1; j <= v; j++) {
                if (!visited[j] && miniDist[j] < miniVal) {
                    miniVal = miniDist[j];
                    curNode = j;
                }
            }
            // 2.标记该节点已被访问
            visited[curNode] = true;
            System.out.println(curNode + "已被选取，距离" + miniVal);
            // 3.更新非访问节点到源点的距离（即更新minDist数组）
            for (int j = 1; j <= v; j++) {
                if (!visited[j] && grid[curNode][j] != Integer.MAX_VALUE && miniDist[curNode] + grid[curNode][j] < miniDist[j]) {
                    miniDist[j] = miniDist[curNode] + grid[curNode][j];
                }
            }
        }

        if (miniDist[v] == Integer.MAX_VALUE){
            System.out.println(-1); // 不能到达终点
        } else {
            System.out.println(miniDist[v]); // 到达终点最短路径
        }

    }
}
